about $834 US your quote seems high to me but there is alot of work to get the heater core out. All you can do is get another quote and compare assuming each shop does quality work. Find out what heater core they are using, OEM, china, Tiawon or ????????. Also ask about their warranty on P&L.
I doubt if the belt streches that much with age, most likely when the tensioner reaches max extension it can no longer provide proper tension to the belt and that could be the problem.